{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Reorder Array to Get Same BST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #union-find #binary-search-tree #memoization #array #math #divide-and-conquer #dynamic-programming #binary-tree #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #并查集 #二叉搜索树 #记忆化搜索 #数组 #数学 #分治 #动态规划 #二叉树 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numOfWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将子数组重新排序得到同一个二叉搜索树的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>nums</code>&nbsp;表示 <code>1</code>&nbsp;到 <code>n</code>&nbsp;的一个排列。我们按照元素在 <code>nums</code>&nbsp;中的顺序依次插入一个初始为空的二叉搜索树（BST）。请你统计将 <code>nums</code>&nbsp;重新排序后，统计满足如下条件的方案数：重排后得到的二叉搜索树与 <code>nums</code>&nbsp;原本数字顺序得到的二叉搜索树相同。</p>\n",
    "\n",
    "<p>比方说，给你&nbsp;<code>nums = [2,1,3]</code>，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组&nbsp;<code>[2,3,1]</code>&nbsp;也能得到相同的 BST，但&nbsp;<code>[3,2,1]</code>&nbsp;会得到一棵不同的&nbsp;BST 。</p>\n",
    "\n",
    "<p>请你返回重排 <code>nums</code>&nbsp;后，与原数组 <code>nums</code> 得到相同二叉搜索树的方案数。</p>\n",
    "\n",
    "<p>由于答案可能会很大，请将结果对<strong>&nbsp;</strong><code>10^9 + 7</code>&nbsp;取余数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/30/bb.png\" style=\"height: 101px; width: 121px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,1,3]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>我们将 nums 重排， [2,3,1] 能得到相同的 BST 。没有其他得到相同 BST 的方案了。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/30/ex1.png\" style=\"height: 161px; width: 241px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,4,5,1,2]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>下面 5 个数组会得到相同的 BST：\n",
    "[3,1,2,4,5]\n",
    "[3,1,4,2,5]\n",
    "[3,1,4,5,2]\n",
    "[3,4,1,2,5]\n",
    "[3,4,1,5,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/30/ex4.png\" style=\"height: 161px; width: 121px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>没有别的排列顺序能得到相同的 BST 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= nums.length</code></li>\n",
    "\t<li><code>nums</code>&nbsp;中所有数 <strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-reorder-array-to-get-same-bst](https://leetcode.cn/problems/number-of-ways-to-reorder-array-to-get-same-bst/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-reorder-array-to-get-same-bst](https://leetcode.cn/problems/number-of-ways-to-reorder-array-to-get-same-bst/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3]', '[3,4,5,1,2]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        M = int(1e9 + 7)\n",
    "        # 三色 f1, 双色 f2\n",
    "        f1 = f2 = 6\n",
    "        for i in range(1, n):\n",
    "            # 每个三色的下一行, 有 2 个三色, 2 个双色\n",
    "            # 每个双色的下一行, 有 2 个三色, 3 个双色\n",
    "            nf1 = f1 * 2 + f2 * 2\n",
    "            nf2 = f1 * 2 + f2 * 3\n",
    "            f1, f2 = nf1 % M, nf2 % M\n",
    "        return (f1 + f2) % M\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        # 121 -> 212 213 232 312 313  a -> 3a 2b\n",
    "        # 123 -> 212 231 232 312      b -> 2a 2b\n",
    "        a = 6\n",
    "        b = 6\n",
    "        ans = 12\n",
    "        for i in range(1, n):\n",
    "            ans = (a * 5 + b * 4) % MOD\n",
    "            a, b = (3 * a + 2 * b) % MOD, (2 * a + 2 * b) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        cons = 10 **9 + 7\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA% cons\n",
    "            ABC = new_ABC% cons\n",
    "        ans = ABA + ABC\n",
    "        return ans % cons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        dp=[1]*12\n",
    "        for _ in range(n-1):\n",
    "            dpx=[0]*12\n",
    "            dpx[0]=(dp[1]+dp[4]+dp[10]+dp[2]+dp[5])%MOD\n",
    "            dpx[3]=(dp[1]+dp[7]+dp[10]+dp[2])%MOD\n",
    "            dpx[6]=(dp[1]+dp[4]+dp[2]+dp[5]+dp[11])%MOD\n",
    "            dpx[9]=(dp[4]+dp[5]+dp[8]+dp[11])%MOD\n",
    "\n",
    "            dpx[1]=(dp[0]+dp[3]+dp[6]+dp[8]+dp[11])%MOD\n",
    "            dpx[4]=(dp[0]+dp[6]+dp[9]+dp[8])%MOD\n",
    "            dpx[7]=(dp[3]+dp[2]+dp[5]+dp[11])%MOD\n",
    "            dpx[10]=(dp[0]+dp[3]+dp[5]+dp[8]+dp[11])%MOD\n",
    "\n",
    "            dpx[2]=(dp[0]+dp[3]+dp[6]+dp[7])%MOD\n",
    "            dpx[5]=(dp[0]+dp[6]+dp[9]+dp[7]+dp[10])%MOD\n",
    "            dpx[8]=(dp[9]+dp[1]+dp[4]+dp[10])%MOD\n",
    "            dpx[11]=(dp[6]+dp[9]+dp[1]+dp[7]+dp[10])%MOD\n",
    "            dp=dpx\n",
    "        return sum(dp)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        fi0, fi1 = 6, 6\n",
    "        for i in range(2, n + 1):\n",
    "            fi0, fi1 = (2 * fi0 + 2 * fi1) % mod, (2 * fi0 + 3 * fi1) % mod\n",
    "        return (fi0 + fi1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        x=6\n",
    "        y=6\n",
    "        t=10**9+7\n",
    "        while n>1:\n",
    "            y=x*2+y*2\n",
    "            x=x+y\n",
    "            n-=1\n",
    "            if x>=t:\n",
    "                x=x%t\n",
    "            if y>=t:\n",
    "                y=y%t\n",
    "\n",
    "        return (x+y)%(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp0=dp1=6\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(1,n):\n",
    "            old_dp0,old_dp1=dp0,dp1\n",
    "            dp0=old_dp0*2+old_dp1*2\n",
    "            dp1=old_dp0*2+old_dp1*3\n",
    "            dp0%=mod\n",
    "            dp1%=mod\n",
    "        return (dp0+dp1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        cons = 10 **9 + 7\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA% cons\n",
    "            ABC = new_ABC% cons\n",
    "        ans = ABA + ABC\n",
    "        return ans % cons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        f0,f1 = 6,6\n",
    "        for i in range(2,n+1):\n",
    "            f0,f1 = (2*f0+2*f1)%MOD,(2*f0+3*f1)%MOD\n",
    "        return (f0+f1)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        cons = 10 **9 + 7\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA% cons\n",
    "            ABC = new_ABC% cons\n",
    "        ans = ABA + ABC\n",
    "        return ans % cons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        x=6\n",
    "        y=6\n",
    "        t=10**9+7\n",
    "        while n>1:\n",
    "            y=x*2+y*2\n",
    "            x=x+y\n",
    "            n-=1\n",
    "            if x>=t:\n",
    "                x=x%t\n",
    "            if y>=t:\n",
    "                y=y%t\n",
    "\n",
    "        return (x+y)%(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        fi0, fi1 = 6, 6\n",
    "        for i in range(2, n + 1):\n",
    "            fi0, fi1 = (2 * fi0 + 2 * fi1) % mod, (2 * fi0 + 3 * fi1) % mod\n",
    "        return (fi0 + fi1) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        data=[]\n",
    "        for x in range(3):\n",
    "            for y in range(3):\n",
    "                for z in range(3):\n",
    "                    if x!=y and y!=z:\n",
    "                        data.append([x,y,z])\n",
    "\n",
    "        maps={}\n",
    "        for i in range(len(data)-1):\n",
    "            for j in range(i+1,len(data)):\n",
    "                if data[i][0]!=data[j][0] and data[i][1]!=data[j][1] and data[i][2]!=data[j][2]:\n",
    "                    if i not in maps:\n",
    "                        maps[i]=[]\n",
    "                    if j not in maps:\n",
    "                        maps[j]=[]\n",
    "                    maps[i].append(j)\n",
    "                    maps[j].append(i)\n",
    "        ans = [1 for _ in range(len(maps))]\n",
    "        lenth = len(ans)\n",
    "        for i in range(n-1):\n",
    "            newans = [0 for _ in range(lenth)]\n",
    "            for idx in range(lenth):\n",
    "                for j in maps[idx]:\n",
    "                    newans[idx] += ans[j]\n",
    "                newans[idx] %= mod\n",
    "            ans = newans\n",
    "        return sum(ans)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "      aba = 6\n",
    "      abc = 6\n",
    "\n",
    "      for _ in range(1, n):\n",
    "        abc = 2 * (aba + abc)\n",
    "        aba += abc\n",
    "        \n",
    "      return (aba + abc) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        t = []\n",
    "        for i in ['0', '1', '2']:\n",
    "            for j in ['0', '1', '2']:\n",
    "                for k in ['0', '1', '2']:\n",
    "                    if i != j and j != k:\n",
    "                        t.append(i + j + k)\n",
    "        dp = [1] * 12\n",
    "        edge = []\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(12):\n",
    "            edge.append([])\n",
    "            for j in range(12):\n",
    "                if self.check(t[i], t[j]):\n",
    "                    edge[i].append(j)\n",
    "        for L in range(n - 1):\n",
    "            dp2 = [0] * 12\n",
    "            for i in range(12):\n",
    "                for j in edge[i]:\n",
    "                    dp2[i] += dp[j]\n",
    "            dp = [x % mod for x in dp2]\n",
    "            \n",
    "        return sum(dp) % mod\n",
    "\n",
    "    def check(self, x, y):\n",
    "        for i in range(len(x)):\n",
    "            if x[i] == y[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp0=dp1=6\n",
    "        mod = 10**9 + 7\n",
    "        for _ in range(1,n):\n",
    "            dp0,dp1=(dp0*2+dp1*2)%mod,(dp0*2+dp1*3)%mod\n",
    "        return (dp0+dp1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numOfWays(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        NUM = 1e9 + 7\n",
    "        f0, f1= 6, 6\n",
    "        for i in range(2, n+1):\n",
    "            f0, f1 = (2*f0+2*f1) % NUM, (2*f0+3*f1)%NUM\n",
    "        return int((f0 + f1) % NUM)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        aba = 6\n",
    "        abc = 6\n",
    "        mask = 10**9+7\n",
    "        for i in range(1, n):\n",
    "            naba = (3*aba)+(2*abc)\n",
    "            nabc = (2*aba)+(2*abc)\n",
    "            aba, abc = naba%mask, nabc%mask\n",
    "        return (aba+abc)%mask\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        cons = 10 **9 + 7\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = (3*ABA + 2*ABC)% cons\n",
    "            new_ABC = (2*ABA + 2*ABC)% cons\n",
    "            ABA = new_ABA\n",
    "            ABC = new_ABC\n",
    "        ans = ABA + ABC\n",
    "        return ans % cons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = (10**9) + 7\n",
    "        a, b = 1, 1\n",
    "        for i in range(n-1):\n",
    "            b = ((a + b) * 2) % MOD\n",
    "            a = (b + a) % MOD\n",
    "        return (a + b) * 6 % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numOfWays(self, n: int) -> int:\r\n",
    "        mod = 10 ** 9 + 7\r\n",
    "        strs = [\"rbg\",\"rbr\",\"rgb\",\"rgr\",\"brg\",\"bgr\",\"bgb\",\"brb\",\"gbr\",\"grb\",\"gbg\",\"grg\"]\r\n",
    "        mapping = [[] for _ in range(12)]\r\n",
    "        for i in range(12):\r\n",
    "            for j in range(i + 1, 12):\r\n",
    "                if all(x != y for x, y in zip(strs[i], strs[j])):\r\n",
    "                    mapping[i].append(j)\r\n",
    "                    mapping[j].append(i)\r\n",
    "        dp = [[0] * 12 for _ in range(2)]\r\n",
    "        for i in range(12):\r\n",
    "            dp[1][i] = 1\r\n",
    "        for i in range(2, n + 1):\r\n",
    "            for j in range(12):\r\n",
    "                res = 0\r\n",
    "                for x in mapping[j]:\r\n",
    "                    res = (res + dp[(i - 1) % 2][x]) % mod\r\n",
    "                dp[i % 2][j] = res\r\n",
    "        return sum(dp[n % 2]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        t = p = 6\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n - 1):\n",
    "            x, y = t, p\n",
    "            t = (3 * x + 2 * y) % mod\n",
    "            p = (2 * x + 2 * y) % mod\n",
    "        return (t + p) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MODULO = 10 ** 9 + 7\n",
    "        fi0, fi1 = 6, 6\n",
    "        for i in range(2, n + 1):\n",
    "            fi0, fi1 = (2 * fi0 + 2 * fi1) % MODULO, (2 * fi0 + 3 * fi1) %MODULO\n",
    "        return (fi0 + fi1) % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        a = 6\n",
    "        b = 6\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            a, b = (3 * a + 2 * b) % mod, (2 * a + 2 * b) % mod\n",
    "        \n",
    "        return (a + b) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numOfWays(self, n: int) -> int:\r\n",
    "        mod = 10 ** 9 + 7\r\n",
    "        strs = [\"rbg\",\"rbr\",\"rgb\",\"rgr\",\"brg\",\"bgr\",\"bgb\",\"brb\",\"gbr\",\"grb\",\"gbg\",\"grg\"]\r\n",
    "        mapping = [[] for _ in range(12)]\r\n",
    "        for i in range(12):\r\n",
    "            for j in range(12):\r\n",
    "                if all(x != y for x, y in zip(strs[i], strs[j])):\r\n",
    "                    mapping[i].append(j)\r\n",
    "        dp = [[1] * 12 for _ in range(2)]\r\n",
    "        for i in range(2, n + 1):\r\n",
    "            for j in range(12):\r\n",
    "                dp[i % 2][j] = sum(dp[(i + 1) % 2][x] for x in mapping[j]) % mod\r\n",
    "        return sum(dp[n % 2]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        # def isValid(row1:list[int],row2:list[int]) -> bool:\n",
    "        #     for i in range(3):\n",
    "        #         if row1[i]==row2[i]:\n",
    "        #             return False\n",
    "        #     return True\n",
    "        # rows=[[1,2,1],[1,2,3],[1,3,1],[1,3,2],[2,1,2],[2,1,3],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,3]]\n",
    "        # transferMatrix=[[0 for _ in range(len(rows))] for _ in range(len(rows))]\n",
    "        # for _ in range(len(rows)):\n",
    "        #     for __ in range(len(rows)):\n",
    "        #         if isValid(rows[_],rows[__]):\n",
    "        #             transferMatrix[_][__]=1\n",
    "\n",
    "        # counts=[1 for _ in range(len(rows))]\n",
    "        # for layers in range(n-1):\n",
    "        #     newCounts=[0 for _ in range(len(rows))]\n",
    "        #     for Prev in range(len(rows)):\n",
    "        #         for Next in range(len(rows)):\n",
    "        #             newCounts[Next]+=counts[Prev]*transferMatrix[Prev][Next]\n",
    "        #     counts=newCounts.copy()\n",
    "        # answer=0\n",
    "        # for _ in range(len(rows)):\n",
    "        #     answer+=counts[_]\n",
    "        # return mod(answer,10**9+7)\n",
    "\n",
    "        transferMatrix=[[2,2],[2,3]]\n",
    "        counts=[6,6]\n",
    "        for layers in range(n-1):\n",
    "            counts=[counts[0]*2+counts[1]*2,counts[0]*2+counts[1]*3]\n",
    "        return mod(counts[0]+counts[1],10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        abc,aba,ans = 6,6,0\n",
    "        for i in range(n):\n",
    "            ans = abc + aba\n",
    "            abc,aba = abc * 2 + aba * 2 , abc * 2 + aba * 3\n",
    "        mod = 10**9 + 7\n",
    "        ans = ans % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        A, B = 6, 6\n",
    "        M = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            A, B = 3 * A + 2 * B, 2 * A + 2 * B\n",
    "        return (A + B) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        abc,aba,ans = 6,6,0\n",
    "        for i in range(n):\n",
    "            ans = abc + aba\n",
    "            abc,aba = abc * 2 + aba * 2 , abc * 2 + aba * 3\n",
    "        mod = 10**9 + 7\n",
    "        ans = ans % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA\n",
    "            ABC = new_ABC\n",
    "        ans = ABA + ABC\n",
    "        return ans % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        a = 6\n",
    "        b = 6\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            a, b = 3 * a + 2 * b, 2 * a + 2 * b\n",
    "        \n",
    "        return (a + b) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA\n",
    "            ABC = new_ABC\n",
    "        ans = ABA + ABC\n",
    "        return ans % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if not n:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 12\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a, b = 6, 6\n",
    "        for i in range(2, n + 1):\n",
    "            x = a * 3 + b * 2\n",
    "            y = a * 2 + b * 2\n",
    "            a, b = x, y \n",
    "\n",
    "        return (a + b) % MOD "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        def isValid(row1:list[int],row2:list[int]) -> bool:\n",
    "            for i in range(3):\n",
    "                if row1[i]==row2[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        rows=[[1,2,1],[1,2,3],[1,3,1],[1,3,2],[2,1,2],[2,1,3],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,3]]\n",
    "        transferMatrix=[[0 for _ in range(len(rows))] for _ in range(len(rows))]\n",
    "        for _ in range(len(rows)):\n",
    "            for __ in range(len(rows)):\n",
    "                if isValid(rows[_],rows[__]):\n",
    "                    transferMatrix[_][__]=1\n",
    "        counts=[1 for _ in range(len(rows))]\n",
    "        for layers in range(n-1):\n",
    "            newCounts=[0 for _ in range(len(rows))]\n",
    "            for Prev in range(len(rows)):\n",
    "                for Next in range(len(rows)):\n",
    "                    newCounts[Next]+=counts[Prev]*transferMatrix[Prev][Next]\n",
    "            counts=newCounts.copy()\n",
    "        answer=0\n",
    "        for _ in range(len(rows)):\n",
    "            answer=mod(answer+counts[_],10**9+7)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        types = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        m = len(types)\n",
    "        valid = [[0 for _ in range(m)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                x1, x2, x3 = types[i] // 9, types[i] // 3 % 3, types[i] % 3 \n",
    "                y1, y2, y3 = types[j] // 9, types[j] // 3 % 3, types[j] % 3 \n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    valid[i][j] = valid[j][i] = 1 \n",
    "        dp = [1] * m\n",
    "        for i in range(2, n + 1):\n",
    "            new = [0] * m \n",
    "            for cur in range(m):\n",
    "                for pre in range(m):\n",
    "                    if valid[pre][cur]:\n",
    "                        new[cur] += dp[pre]\n",
    "                        # new[cur] %= 10 ** 9 + 7\n",
    "            dp = new \n",
    "        return sum(dp) % (10 ** 9 + 7)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        def isValid(row1:list[int],row2:list[int]) -> bool:\n",
    "            for i in range(3):\n",
    "                if row1[i]==row2[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        rows=[[1,2,1],[1,2,3],[1,3,1],[1,3,2],[2,1,2],[2,1,3],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,3]]\n",
    "        transferMatrix=[[0 for _ in range(len(rows))] for _ in range(len(rows))]\n",
    "        for _ in range(len(rows)):\n",
    "            for __ in range(len(rows)):\n",
    "                if isValid(rows[_],rows[__]):\n",
    "                    transferMatrix[_][__]=1\n",
    "        counts=[1 for _ in range(len(rows))]\n",
    "        for layers in range(n-1):\n",
    "            newCounts=[0 for _ in range(len(rows))]\n",
    "            for Prev in range(len(rows)):\n",
    "                for Next in range(len(rows)):\n",
    "                    newCounts[Next]+=counts[Prev]*transferMatrix[Prev][Next]\n",
    "            counts=newCounts.copy()\n",
    "        answer=0\n",
    "        for _ in range(len(rows)):\n",
    "            answer+=counts[_]\n",
    "        return mod(answer,10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp=[[0]*2 for _ in range(n)]\n",
    "        dp[0][0]=dp[0][1]=6\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]+=dp[i-1][0]*2\n",
    "            dp[i][0]+=dp[i-1][1]*2\n",
    "            dp[i][1]+=dp[i-1][0]*2\n",
    "            dp[i][1]+=dp[i-1][1]*3\n",
    "            dp[i][0]%=mod\n",
    "            dp[i][1]%=mod\n",
    "        return sum(dp[n-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        def isValid(row1:list[int],row2:list[int]) -> bool:\n",
    "            for i in range(3):\n",
    "                if row1[i]==row2[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        rows=[[1,2,1],[1,2,3],[1,3,1],[1,3,2],[2,1,2],[2,1,3],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,3]]\n",
    "        transferMatrix=[[0 for _ in range(len(rows))] for _ in range(len(rows))]\n",
    "        for _ in range(len(rows)):\n",
    "            for __ in range(len(rows)):\n",
    "                if isValid(rows[_],rows[__]):\n",
    "                    transferMatrix[_][__]=1\n",
    "        counts=[1 for _ in range(len(rows))]\n",
    "        for layers in range(n-1):\n",
    "            newCounts=[0 for _ in range(len(rows))]\n",
    "            for Prev in range(len(rows)):\n",
    "                for Next in range(len(rows)):\n",
    "                    newCounts[Next]+=counts[Prev]*transferMatrix[Prev][Next]\n",
    "            counts=newCounts.copy()\n",
    "        answer=0\n",
    "        for _ in range(len(rows)):\n",
    "            answer+=counts[_]\n",
    "        return mod(answer,10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        s=n\n",
    "        dp=[[0]*2 for _ in range(n)]\n",
    "        \n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        mod=10**9+7\n",
    "        for i in range(1,n):\n",
    "          dp[i][0]=(dp[i-1][0]*3+dp[i-1][1]*2)%mod\n",
    "          dp[i][1]=(dp[i-1][0]*2+dp[i-1][1]*2)%mod\n",
    "       #print(dp)\n",
    "        return sum(dp[-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        f = [[0] * 2 for _ in range(n + 1)]\n",
    "\n",
    "        # abc\n",
    "        f[1][0] = 6\n",
    "        # aba\n",
    "        f[1][1] = 6\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            f[i][0] = (f[i-1][0] * 3 + f[i-1][1] * 2) % mod\n",
    "            f[i][1] = (f[i-1][0] * 2 + f[i-1][1] * 2 ) % mod\n",
    "        \n",
    "        return sum(f[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 预处理出所有满足条件的 type\n",
    "        types = list()\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        # 只要相邻的颜色不相同就行\n",
    "                        # 将其以十进制的形式存储\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        type_cnt = len(types)\n",
    "        # 预处理出所有可以作为相邻行的 type 对\n",
    "        related = [[0] * type_cnt for _ in range(type_cnt)]\n",
    "        for i, ti in enumerate(types):\n",
    "            # 得到 types[i] 三个位置的颜色\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                # 得到 types[j] 三个位置的颜色\n",
    "                y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3\n",
    "                # 对应位置不同色，才能作为相邻的行\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    related[i][j] = 1\n",
    "        # 递推数组\n",
    "        f = [[0] * type_cnt for _ in range(n + 1)]\n",
    "        # 边界情况，第一行可以使用任何 type\n",
    "        f[1] = [1] * type_cnt\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(type_cnt):\n",
    "                for k in range(type_cnt):\n",
    "                    # f[i][j] 等于所有 f[i - 1][k] 的和\n",
    "                    # 其中 k 和 j 可以作为相邻的行\n",
    "                    if related[k][j]:\n",
    "                        f[i][j] += f[i - 1][k]\n",
    "                        f[i][j] %= mod\n",
    "        # 最终所有的 f[n][...] 之和即为答案\n",
    "        ans = sum(f[n]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        kind = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        kind.append(f'{i}{j}{k}')\n",
    "        # print(kind)\n",
    "        m = len(kind)\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        for i in range(m):\n",
    "            f[0][i] = 1\n",
    "        # d = [[0] * m for _ in range(m)]\n",
    "        # for i in range(m):\n",
    "        #     for j in range(m):\n",
    "        #         if all(kind[i][k] != kind[j][k] for k in range(3)]:\n",
    "        #             d[i][j] = 1 \n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if all(kind[j][p] != kind[k][p] for p in range(3)):\n",
    "                        f[i][j] = (f[i][j] + f[i - 1][k]) % MOD\n",
    "        return sum(f[n - 1]) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        types = []\n",
    "        for i in range (3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        \n",
    "        m = len(types)\n",
    "        match = [[0] * m for _ in range(m)]\n",
    "        for i, ti in enumerate(types):\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                y1, y2, y3 = tj // 9, tj //3 % 3, tj % 3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    match[i][j] = 1\n",
    "        \n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[1] = [1] * 12\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if match[j][k]:\n",
    "                        f[i][j] = (f[i][j] + f[i-1][k]) % mod\n",
    "        \n",
    "        return sum(f[-1]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        # 与处理出type\n",
    "        types = list()\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        type_cnt = len(types)\n",
    "        match = [[0] * type_cnt for _ in range(type_cnt)]\n",
    "\n",
    "        for i, ti in enumerate(types):\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    match[i][j] = 1\n",
    "        \n",
    "        # 递推\n",
    "        f = [[0] * type_cnt for _ in range(n + 1)]\n",
    "        f[1] = [1] * type_cnt\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(type_cnt):\n",
    "                for k in range(type_cnt):\n",
    "                    # j接在k的后面\n",
    "                    if match[k][j]:\n",
    "                        f[i][j] =  (f[i][j] + f[i-1][k]) % mod\n",
    "        return sum(f[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 预处理出所有满足条件的 type\n",
    "        types = list()\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        # 只要相邻的颜色不相同就行\n",
    "                        # 将其以十进制的形式存储\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        type_cnt = len(types)\n",
    "        # 预处理出所有可以作为相邻行的 type 对\n",
    "        related = [[0] * type_cnt for _ in range(type_cnt)]\n",
    "        for i, ti in enumerate(types):\n",
    "            # 得到 types[i] 三个位置的颜色\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                # 得到 types[j] 三个位置的颜色\n",
    "                y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3\n",
    "                # 对应位置不同色，才能作为相邻的行\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    related[i][j] = 1\n",
    "        # 递推数组\n",
    "        f = [[0] * type_cnt for _ in range(n + 1)]\n",
    "        # 边界情况，第一行可以使用任何 type\n",
    "        f[1] = [1] * type_cnt\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(type_cnt):\n",
    "                for k in range(type_cnt):\n",
    "                    # f[i][j] 等于所有 f[i - 1][k] 的和\n",
    "                    # 其中 k 和 j 可以作为相邻的行\n",
    "                    if related[k][j]:\n",
    "                        f[i][j] += f[i - 1][k]\n",
    "                        f[i][j] %= mod\n",
    "        # 最终所有的 f[n][...] 之和即为答案\n",
    "        ans = sum(f[n]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        types = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        typesCnt = len(types)\n",
    "        # 预处理出所有可以作为相邻行的 type 对\n",
    "        canType = [[0] * typesCnt for _ in range(typesCnt)]\n",
    "        for i in range(typesCnt):\n",
    "            for j in range(typesCnt):\n",
    "                if i != j:\n",
    "                    a = [types[i] // 9, (types[i] % 9) // 3, types[i] % 3]\n",
    "                    b = [types[j] // 9, (types[j] % 9) // 3, types[j] % 3]\n",
    "                    if a[0] != b[0] and a[1] != b[1] and a[2] != b[2]:\n",
    "                        canType[i][j] = 1\n",
    "\n",
    "        dp = [[0] * typesCnt for _ in range(n)]\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(typesCnt):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(typesCnt):\n",
    "                for k in range(typesCnt):\n",
    "                    if canType[j][k] == 1:\n",
    "                        dp[i][j] += dp[i - 1][k]\n",
    "                        dp[i][j] %= mod\n",
    "        return sum(x % mod for x in dp[n - 1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        types = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        \n",
    "        m = len(types)\n",
    "        match = [[0] * m for _ in range(m)]\n",
    "\n",
    "        for i, ti in enumerate(types):\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    match[i][j] = 1\n",
    "        \n",
    "        # 递推\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[1] = [1] * m\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if match[k][j]:\n",
    "                        f[i][j] = (f[i][j] + f[i-1][k]) % mod\n",
    "        \n",
    "        return sum(f[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        types = []\n",
    "        for i in range (3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        \n",
    "        m = len(types)\n",
    "        match = [[0] * m for _ in range(m)]\n",
    "        for i, ti in enumerate(types):\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                y1, y2, y3 = tj // 9, tj //3 % 3, tj % 3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    match[i][j] = 1\n",
    "        \n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[1] = [1] * m\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if match[j][k]:\n",
    "                        f[i][j] = (f[i][j] + f[i-1][k]) % mod\n",
    "        \n",
    "        return sum(f[-1]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        # 红：2,黄：1,绿,0 用一个三进制数表示一行的颜色方案\n",
    "        # 然后会得到一个所有无重复的一行颜色方案共12种，放入一个集合\n",
    "        # 枚举这12种方案，对于其中一种方案mask，其d[mask]:mask'表示与mask不重复的颜色方案\n",
    "        # dp[i][mask] = sum(dp[i-1][mask'] for mask' in d[mask])\n",
    "        # return sum(dp[0][mask] for mask in 12种方案)\n",
    "        # 预处理12种方案\n",
    "        masks = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        masks.append(i*9+j*3+k)\n",
    "        \n",
    "        m = len(masks)\n",
    "        # d[i][j]表示i,j两行可以作为相邻的两行，也就是无重复的两行\n",
    "        d = [[0]*m for _ in range(m)]\n",
    "        # 预处理d\n",
    "        for i,vi in enumerate(masks):\n",
    "            # 取每一位和十进制一样，110,110//100,110//10%10,110%10\n",
    "            x1,x2,x3 = vi//9,vi//3%3,vi%3\n",
    "            for j,vj in enumerate(masks):\n",
    "                y1,y2,y3 = vj//9,vj//3%3,vj%3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    d[i][j] = 1\n",
    "        # 动态规划\n",
    "        f = [[0]*m for _ in range(n)]\n",
    "        f[0] = [1]*m\n",
    "        for i in range(1,n):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if d[j][k]:\n",
    "                        f[i][j] += f[i-1][k]\n",
    "                        f[i][j] %= mod\n",
    "        return sum(f[n-1])%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        masks = []\n",
    "        # 统计12种方案\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        masks.append(i*9+j*3+k)\n",
    "        # dp[i][k]表示第i行涂色方案为k有多少种涂色方案\n",
    "        # dp[i-1][k']，k'表示与k涂色方案不重合的方案\n",
    "        m = len(masks)\n",
    "        d = [[0]*m for _ in range(m)]\n",
    "        for i,s1 in enumerate(masks):\n",
    "            for j,s2 in enumerate(masks):\n",
    "                x1,x2,x3 = s1//9,s1//3%3,s1%3\n",
    "                y1,y2,y3 = s2//9,s2//3%3,s2%3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    d[i][j] = 1\n",
    "        # 动态规划\n",
    "        dp = [[0]*m for _ in range(n)]\n",
    "        dp[0] = [1]*m\n",
    "        for i in range(1,n):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if d[j][k]:\n",
    "                        dp[i][j] += dp[i-1][k]\n",
    "                        dp[i][j] %= mod\n",
    "        return sum(dp[n-1])%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [[0] * 12 for _ in range(5000)]\n",
    "dp[0] = [1] * 12\n",
    "# 0 = 4 + 5 + 7 + 8 + 9\n",
    "# 1 = 4 + 6 + 7 + 8\n",
    "# 2 = 4 + 5 + 8 + 9 + 11\n",
    "# 3 = 5 + 9 + 10 + 11\n",
    "# 4 = 0 + 1 + 2 +10 + 11\n",
    "# 5 = 0 + 2 + 3 + 10\n",
    "# 6 = 1 + 8 + 9 + 11\n",
    "# 7 = 0 + 1 + 9 + 10 + 11\n",
    "# 8 = 0 + 1 + 2 + 6\n",
    "# 9 = 0 + 2 + 3 +6 + 7\n",
    "# 10 = 3 + 4 + 5 + 7\n",
    "# 11 = 2 + 3 + 4 + 6 + 7\n",
    "for i in range(1, 5000):\n",
    "    dp[i][0] = (dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][7] + dp[i - 1][8] + dp[i - 1][9]) % (10 ** 9 + 7)\n",
    "    dp[i][1] = (dp[i - 1][4] + dp[i - 1][6] + dp[i - 1][7] + dp[i - 1][8]) % (10 ** 9 + 7)\n",
    "    dp[i][2] = (dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][8] + dp[i - 1][9] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][3] = (dp[i - 1][5] + dp[i - 1][9] + dp[i - 1][10] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][4] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][10] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][5] = (dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][10]) % (10 ** 9 + 7)\n",
    "    dp[i][6] = (dp[i - 1][1] + dp[i - 1][8] + dp[i - 1][9] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][7] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][9] + dp[i - 1][10] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][8] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][6]) % (10 ** 9 + 7)\n",
    "    dp[i][9] = (dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][6] + dp[i - 1][7]) % (10 ** 9 + 7)\n",
    "    dp[i][10] = (dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][7]) % (10 ** 9 + 7)\n",
    "    dp[i][11] = (dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][6] + dp[i - 1][7]) % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        return sum(dp[n - 1]) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def numOfWays(self, n: int) -> int:\n",
    "        types = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        typesCnt = len(types)\n",
    "        # 预处理出所有可以作为相邻行的 type 对\n",
    "        canType = [[0] * typesCnt for _ in range(typesCnt)]\n",
    "        for i in range(typesCnt):\n",
    "            for j in range(typesCnt):\n",
    "                if i != j:\n",
    "                    a = [types[i] // 9, (types[i] % 9) // 3, types[i] % 3]\n",
    "                    b = [types[j] // 9, (types[j] % 9) // 3, types[j] % 3]\n",
    "                    if a[0] != b[0] and a[1] != b[1] and a[2] != b[2]:\n",
    "                        canType[i][j] = 1\n",
    "\n",
    "        dp = [[0] * typesCnt for _ in range(n)]\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(typesCnt):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(typesCnt):\n",
    "                for k in range(typesCnt):\n",
    "                    if canType[j][k] == 1:\n",
    "                        dp[i][j] += dp[i - 1][k]\n",
    "                        dp[i][j] %= mod\n",
    "        return sum(x % mod for x in dp[n - 1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        # 红：1 黄:2 绿3：\n",
    "        data=[[1, 2, 1], [1, 2, 3], [1, 3, 1], [1, 3, 2],\n",
    "              [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2],\n",
    "              [3, 2, 1], [3, 2, 3], [3, 1, 2], [3, 1, 3]]\n",
    "\n",
    "        nm=12\n",
    "        g=[[1 for i in range(12)] for i in range(12)]\n",
    "        for i in range(nm):\n",
    "            for j in range(nm):\n",
    "                can=True\n",
    "                for k in range(3):\n",
    "                    if data[i][k]==data[j][k]:\n",
    "                        can=False\n",
    "                        break\n",
    "                if can:\n",
    "                    g[i][j],g[j][i]=True,True\n",
    "                else:\n",
    "                    g[i][j],g[j][i]=False,False\n",
    "\n",
    "        dp=[[0 for i in range(nm)] for i in range(n)]\n",
    "        for i in range(12):\n",
    "            dp[0][i]=1\n",
    "\n",
    "        if n==1:return sum(dp[0])\n",
    "        for p in range(1,n):\n",
    "            for i in range(nm):\n",
    "                for j in range(nm):\n",
    "                    if g[i][j]==True:\n",
    "                        dp[p][j]=(dp[p][j]+dp[p-1][i])%(10**9+7)\n",
    "\n",
    "        return sum(dp[n-1])%(10**9+7)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    n=3\n",
    "    test = Solution()\n",
    "    l3 = test.numOfWays(n)\n",
    "    print('l3= %s'%l3)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        # 0,1,2,red,yellow,green\n",
    "        mod = int(1e9 + 7)\n",
    "        # 一行内不冲突\n",
    "        typeList = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i == j or j == k:\n",
    "                        continue\n",
    "                    val = i * 9 + j * 3 + k * 1\n",
    "                    typeList.append(val)\n",
    "        def toBit(i, j, k):\n",
    "            return i * 9 + j * 3 + k * 1\n",
    "\n",
    "\n",
    "        def bitCov(val):\n",
    "            res = [0] * 3\n",
    "            for i in range(3):\n",
    "                div, mod = divmod(val, 3)\n",
    "                res[3 - 1 - i] = mod\n",
    "                val = div\n",
    "            \n",
    "            return res\n",
    "\n",
    "        #行间不冲突\n",
    "        checkMat = [[False] * len(typeList) for _ in range(len(typeList))]\n",
    "        for i in range(len(typeList)):\n",
    "            for j in range(len(typeList)):\n",
    "                \n",
    "                ii = bitCov(typeList[i])\n",
    "                jj = bitCov(typeList[j])\n",
    "\n",
    "                if ii[0] == jj[0] or ii[1] == jj[1] or ii[2] == jj[2]:\n",
    "                    checkMat[i][j] = True\n",
    "        \n",
    "\n",
    "\n",
    "        dp = [[1] * len(typeList) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(2, len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                dp[i][j] = 0\n",
    "                for k in range(len(typeList)):\n",
    "                    dp[i][j] += dp[i - 1][k] if not checkMat[j][k] else 0\n",
    "                    dp[i][j] %= mod\n",
    "        \n",
    "        return sum(dp[-1]) % mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        f = [[0] * 2 for _ in range(n + 1)]\n",
    "        # ABC, ABA\n",
    "        f[1][0] = 6\n",
    "        f[1][1] = 6\n",
    "        for i in range(2, n+1):\n",
    "            f[i][0] = f[i-1][0] * 3 + f[i-1][1] * 2\n",
    "            f[i][1] = f[i-1][0] * 2 + f[i-1][1] * 2\n",
    "        \n",
    "        return sum(f[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mode=10**9+7\n",
    "        # @cache\n",
    "        # def dfs(k,c):\n",
    "        #     if k==n:\n",
    "        #         return 1\n",
    "        #     elif k==0:\n",
    "        #         return 6*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "        #     else:\n",
    "        #         if c==0:\n",
    "        #             return 2*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "        #         else:\n",
    "        #             return (2*dfs(k+1,0)+3*dfs(k+1,1))%mode\n",
    "        # return dfs(0,0)\n",
    "        dp=[[0]*2 for i in range(n)]\n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=3*dp[i-1][0]+dp[i-1][1]*2\n",
    "            dp[i][1]=2*dp[i-1][0]+2*dp[i-1][1]\n",
    "        return (dp[n-1][0]+dp[n-1][1])%mode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp=[[0 for i in range(2)] for j in range(n)]\n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        if n>=2:\n",
    "            for k in range(1,n):\n",
    "                dp[k][0]=dp[k-1][0]*3+dp[k-1][1]*2\n",
    "                dp[k][1]=dp[k-1][0]*2+dp[k-1][1]*2\n",
    "        return (dp[n-1][0]+dp[n-1][1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        '''\n",
    "        上一行是双色ABA:下一行情况：双色：BAB,BCB,CAC, 三色：BAC,CAB\n",
    "        上一行是三色ABC:下一行情况: 双色：BAB,BCB      三色：BCA,BAC\n",
    "        dp[i][0]表示当前行双色情况的种类数目\n",
    "        dp[i][1]表示当前行三色情况的种类数目\n",
    "        dp[i][0] = dp[i-1][0]*3 + dp[i-1][1]*2\n",
    "        dp[i][1] = dp[i-1][0]*2 + dp[i-1][1]*2\n",
    "        '''\n",
    "        dp = [[0 for i in range(2)] for j in range(n)]\n",
    "        dp[0][0], dp[0][1] = 6, 6\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = dp[i-1][0]*3 + dp[i-1][1]*2\n",
    "            dp[i][1] = dp[i-1][0]*2 + dp[i-1][1]*2\n",
    "        return (dp[-1][0]+dp[-1][1])%(int(1e9+7))\n",
    "\n",
    "# 作者：soiam2014\n",
    "# 链接：https://leetcode.cn/problems/number-of-ways-to-paint-n-3-grid/solutions/199022/5383gei-nx3wang-ge-tu-tu-se-de-fang-an-shu-by-soia/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp=[[0 for i in range(2)] for j in range(n)]\n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        if n>=2:\n",
    "            for k in range(1,n):\n",
    "                dp[k][0]=dp[k-1][0]*3+dp[k-1][1]*2\n",
    "                dp[k][1]=dp[k-1][0]*2+dp[k-1][1]*2\n",
    "        return (dp[n-1][0]+dp[n-1][1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp=[[0 for i in range(2)] for j in range(n)]\n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        if n>=2:\n",
    "            for k in range(1,n):\n",
    "                dp[k][0]=dp[k-1][0]*3+dp[k-1][1]*2\n",
    "                dp[k][1]=dp[k-1][0]*2+dp[k-1][1]*2\n",
    "        return (dp[n-1][0]+dp[n-1][1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#  下层的结果 = ABA类的个数 + ABC类的个数 = (3m+2n) + (2m+2n)\n",
    "MOD = 10 ** 9 + 7\n",
    "rec = {1: (6, 6)}\n",
    "for i in range(2, 50001):\n",
    "    m, n = rec[i - 1]\n",
    "    rec[i] = ((3 * m + 2 * n) % MOD, (2 * m + 2 * n) % MOD)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        return sum(rec[n]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c):#i为当前的行下标，c为上一层是哪种排列\n",
    "            if i == n:#当已经铺满\n",
    "                return 1\n",
    "            elif i == 0:#特殊情况，第一层\n",
    "                return 6 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "            else:\n",
    "                if c == 0:#如果上层为ABC\n",
    "                    return 2 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "                else:#如果上层为ABA\n",
    "                    return (2 * dfs(i + 1, 0) + 3 * dfs(i + 1, 1)) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mode=10**9+7\n",
    "        @cache\n",
    "        def dfs(k,c):\n",
    "            if k==n:\n",
    "                return 1\n",
    "            elif k==0:\n",
    "                return 6*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "            else:\n",
    "                if c==0:\n",
    "                    return 2*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "                else:\n",
    "                    return (2*dfs(k+1,0)+3*dfs(k+1,1))%mode\n",
    "        return dfs(0,0)\n",
    "        # dp=[[0]*2 for i in range(n)]\n",
    "        # dp[0][0]=6\n",
    "        # dp[0][1]=6\n",
    "        # for i in range(1,n):\n",
    "        #     dp[i][0]=3*dp[i-1][0]+dp[i-1][1]*2\n",
    "        #     dp[i][1]=2*dp[i-1][0]+2*dp[i-1][1]\n",
    "        # return (dp[n-1][0]+dp[n-1][1])%mode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c):#i为当前的行下标，c为上一层是哪种排列\n",
    "            if i == n:#当已经铺满\n",
    "                return 1\n",
    "            elif i == 0:#特殊情况，第一层\n",
    "                return 6 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "            else:\n",
    "                if c == 0:#如果上层为ABC\n",
    "                    return 2 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "                else:#如果上层为ABA\n",
    "                    return (2 * dfs(i + 1, 0) + 3 * dfs(i + 1, 1)) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c):#i为当前的行下标，c为上一层是哪种排列\n",
    "            if i == n:#当已经铺满\n",
    "                return 1\n",
    "            elif i == 0:#特殊情况，第一层\n",
    "                return 6 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "            else:\n",
    "                if c == 0:#如果上层为ABC\n",
    "                    return 2 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "                else:#如果上层为ABA\n",
    "                    return (2 * dfs(i + 1, 0) + 3 * dfs(i + 1, 1)) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, 0)\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mode=10**9+7\n",
    "        @cache\n",
    "        def dfs(k,c):\n",
    "            if k==n:\n",
    "                return 1\n",
    "            elif k==0:\n",
    "                return 6*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "            else:\n",
    "                if c==0:\n",
    "                    return 2*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "                else:\n",
    "                    return (2*dfs(k+1,0)+3*dfs(k+1,1))%mode\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        md=10**9+7\n",
    "        arr=[1]*12\n",
    "        while n>1:\n",
    "            newarr=[0]*12\n",
    "            newarr[0]=arr[4]+arr[5]+arr[7]+arr[8]+arr[9]\n",
    "            newarr[1]=arr[4]+arr[6]+arr[7]+arr[8]\n",
    "            newarr[2]=arr[4]+arr[5]+arr[8]+arr[9]+arr[11]\n",
    "            newarr[3]=arr[5]+arr[9]+arr[10]+arr[11]\n",
    "            newarr[4]=arr[0]+arr[1]+arr[2]+arr[10]+arr[11]\n",
    "            newarr[5]=arr[0]+arr[2]+arr[3]+arr[10]\n",
    "            newarr[6]=arr[1]+arr[8]+arr[9]+arr[11]\n",
    "            newarr[7]=arr[0]+arr[1]+arr[9]+arr[10]+arr[11]\n",
    "            newarr[8]=arr[0]+arr[1]+arr[2]+arr[6]\n",
    "            newarr[9]=arr[0]+arr[2]+arr[3]+arr[6]+arr[7]\n",
    "            newarr[10]=arr[3]+arr[4]+arr[5]+arr[7]\n",
    "            newarr[11]=arr[2]+arr[3]+arr[4]+arr[6]+arr[7]\n",
    "            arr=np.array(newarr)%md\n",
    "            n-=1\n",
    "        return int(sum(arr)%md)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos,pre):\n",
    "            if pos==n:return 1\n",
    "            ans=0\n",
    "            \n",
    "            for i in range(3):\n",
    "\n",
    "                for j in range(3):\n",
    "\n",
    "                    for k in range(3):\n",
    "\n",
    "                        temp=(i,j,k)\n",
    "\n",
    "                        if i==j or j==k or i==pre[0] or j==pre[1] or k==pre[2]:\n",
    "                            continue\n",
    "                        ans+=dfs(pos+1,temp)\n",
    "\n",
    "\n",
    "            return ans%mod\n",
    "\n",
    "        return dfs(0,(-1,-1,-1))%mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos,pre):\n",
    "            if pos==n:return 1\n",
    "            ans=0\n",
    "            \n",
    "            for i in range(3):\n",
    "                if i==pre[0]:continue\n",
    "\n",
    "                for j in range(3):\n",
    "                    if j==pre[1]:continue\n",
    "                    if j==i:continue\n",
    "\n",
    "                    for k in range(3):\n",
    "                        if k==pre[2]:continue\n",
    "                        if k==j:continue\n",
    "\n",
    "                        temp=(i,j,k)\n",
    "                        ans+=dfs(pos+1,temp)\n",
    "\n",
    "\n",
    "            return ans%mod\n",
    "\n",
    "        return dfs(0,(-1,-1,-1))%mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        colors = [(0, 1, 0), (1, 0, 1), (2, 0, 1), (0, 1, 2), (1, 0, 2), (2, 0, 2), (0, 2, 0), (1, 2, 0), (2, 1, 0), (0, 2, 1), (1, 2, 1), (2, 1, 2)]\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i, a, b, c) :\n",
    "            if i == n :\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for t1, t2, t3 in colors :\n",
    "                if t1 != a and t2 != b and t3 != c and t1 != t2 and t2 != t3:\n",
    "                    res += (dfs(i+1, t1, t2, t3)) % mod\n",
    "            \n",
    "            return res % mod\n",
    "        \n",
    "        return dfs(0, -1, -1, -1)  % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = 10**9 +7\n",
    "        res = 0\n",
    "        method = [121, 123, 131, 132, 212, 213, 231, 232, 312, 313, 321, 323]\n",
    "        g = [[] for _ in range(12)]\n",
    "        for a in range(12):\n",
    "            for b in range(a):\n",
    "                i, j = method[a], method[b]\n",
    "                if i % 10 != j % 10 and i % 100 // 10 != j % 100 // 10 and i // 100 != j // 100:\n",
    "                    g[a].append(b)\n",
    "                    g[b].append(a)\n",
    "        fun = [[0]*12 for _ in range(n)] + [[1]*12]\n",
    "        for now in range(n-1, 0, -1):\n",
    "            for i in range(11, -1, -1):\n",
    "                for nex in g[i]:\n",
    "                    fun[now][i] += fun[now+1][nex]\n",
    "        return sum(fun[1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = 10**9 +7\n",
    "        g = [[4,5,7,8,9],[4,6,7,8],[4,5,8,9,11],[5,9,10,11],[0,1,2,10,11],[0,2,3,10],[1,8,9,11],[0,1,9,10,11],[0,1,2,6],[0,2,3,6,7],[3,4,5,7],[2,3,4,6,7]]\n",
    "        fun = [[0]*12 for _ in range(n)] + [[1]*12]\n",
    "        for now in range(n-1, 0, -1):\n",
    "            for i in range(11, -1, -1):\n",
    "                for nex in g[i]:\n",
    "                    fun[now][i] += fun[now+1][nex]\n",
    "        return sum(fun[1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinarySearchTreeByArray:\n",
    "    # 模板：根据数组生成二叉树的有向图结构\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def build(nums: List[int]):\n",
    "        n = len(nums)\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda it: nums[it])  # 索引\n",
    "        rank = {idx: i for i, idx in enumerate(ind)}  # 排序\n",
    "\n",
    "        dct = [[] for _ in range(n)]  # 二叉树按照索引的有向图结构\n",
    "        uf = UnionFindSpecial(n)\n",
    "        post = {}\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = rank[i]\n",
    "            if x + 1 in post:\n",
    "                r = uf.find(post[x + 1])\n",
    "                dct[i].append(r)\n",
    "                uf.union(i, r)\n",
    "            if x - 1 in post:\n",
    "                r = uf.find(post[x - 1])\n",
    "                dct[i].append(r)\n",
    "                uf.union(i, r)\n",
    "            post[x] = i\n",
    "        return dct\n",
    "\n",
    "    @staticmethod\n",
    "    def build_with_stack(nums: List[int]):\n",
    "        # 模板：按顺序生成二叉树，返回二叉树的索引父子信息\n",
    "        n = len(nums)\n",
    "        # 先按照大小关系编码成 1..n\n",
    "        lst = sorted(nums)\n",
    "        dct = {num: i + 1 for i, num in enumerate(lst)}\n",
    "        ind = {num: i for i, num in enumerate(nums)}\n",
    "        order = [dct[i] for i in nums]\n",
    "        father, occur, stack = [0] * (n + 1), [0] * (n + 1), []\n",
    "        deep = [0] * (n + 1)\n",
    "        for i, x in enumerate(order, 1):\n",
    "            occur[x] = i\n",
    "        # 记录原数组索引的父子关系\n",
    "        for x, i in enumerate(occur):\n",
    "            while stack and occur[stack[-1]] > i:\n",
    "                if occur[father[stack[-1]]] < i:\n",
    "                    father[stack[-1]] = x\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                father[x] = stack[-1]\n",
    "            stack.append(x)\n",
    "\n",
    "        for x in order:\n",
    "            deep[x] = 1 + deep[father[x]]\n",
    "\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i in range(1, n + 1):\n",
    "            if father[i]:\n",
    "                u, v = father[i]-1, i-1\n",
    "                x, y = ind[lst[u]], ind[lst[v]]\n",
    "                dct[x].append(y)\n",
    "\n",
    "        return dct\n",
    "\n",
    "mod = 10**9 + 7\n",
    "class Combinatorics:\n",
    "    def __init__(self, n, mod):\n",
    "        # 模板：求全排列组合数，使用时注意 n 的取值范围\n",
    "        n += 10\n",
    "        self.perm = [1] * n\n",
    "        self.rev = [1] * n\n",
    "        self.mod = mod\n",
    "        for i in range(1, n):\n",
    "            # 阶乘数 i! 取模\n",
    "            self.perm[i] = self.perm[i - 1] * i\n",
    "            self.perm[i] %= self.mod\n",
    "        self.rev[-1] = self.mod_reverse(self.perm[-1], self.mod)  # 等价于pow(self.perm[-1], -1, self.mod)\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            self.rev[i] = (self.rev[i + 1] * (i + 1) % mod)  # 阶乘 i! 取逆元\n",
    "        self.fault = [0] * n\n",
    "        self.fault_perm()\n",
    "        return\n",
    "\n",
    "    def ex_gcd(self, a, b):\n",
    "        # 扩展欧几里得求乘法逆元\n",
    "        if b == 0:\n",
    "            return 1, 0, a\n",
    "        else:\n",
    "            x, y, q = self.ex_gcd(b, a % b)\n",
    "            x, y = y, (x - (a // b) * y)\n",
    "            return x, y, q\n",
    "\n",
    "    def mod_reverse(self, a, p):\n",
    "        x, y, q = self.ex_gcd(a, p)\n",
    "        if q != 1:\n",
    "            raise Exception(\"No solution.\")   # 逆元要求a与p互质\n",
    "        else:\n",
    "            return (x + p) % p  # 防止负数\n",
    "\n",
    "    def comb(self, a, b):\n",
    "        if a < b:\n",
    "            return 0\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a] * self.rev[b] * self.rev[a - b]\n",
    "        return res % self.mod\n",
    "\n",
    "    def factorial(self, a):\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a]\n",
    "        return res % self.mod\n",
    "\n",
    "    def fault_perm(self):\n",
    "        # 求错位排列组合数\n",
    "        self.fault[0] = 1\n",
    "        self.fault[2] = 1\n",
    "        for i in range(3, len(self.fault)):\n",
    "            self.fault[i] = (i - 1) * (self.fault[i - 1] + self.fault[i - 2])\n",
    "            self.fault[i] %= self.mod\n",
    "        return\n",
    "\n",
    "    def inv(self, n):\n",
    "        # 求 pow(n, -1, mod)\n",
    "        return self.perm[n - 1] * self.rev[n] % self.mod\n",
    "\n",
    "    def catalan(self, n):\n",
    "        # 求卡特兰数\n",
    "        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod\n",
    "\n",
    "\n",
    "cb = Combinatorics(1000, mod)\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        dct = BinarySearchTreeByArray().build_with_stack(nums)\n",
    "        stack = [0]\n",
    "        n = len(nums)\n",
    "        ans = [0]*n\n",
    "        sub = [0]*n\n",
    "        while stack:\n",
    "            i = stack.pop()\n",
    "            if i >= 0:\n",
    "                stack.append(~i)\n",
    "                for j in dct[i]:\n",
    "                    stack.append(j)\n",
    "            else:\n",
    "                i = ~i\n",
    "                cur_ans = 1\n",
    "                cur_sub = sum(sub[j] for j in dct[i])\n",
    "                sub[i] = cur_sub + 1\n",
    "                for j in dct[i]:\n",
    "                    cur_ans *= cb.comb(cur_sub, sub[j])*ans[j]\n",
    "                    cur_sub -= sub[j]\n",
    "                    cur_ans %= mod\n",
    "                ans[i] = cur_ans\n",
    "        return (ans[0] - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSpecial:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x < root_y:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        return\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "\n",
    "class BinarySearchTreeByArray:\n",
    "    # 模板：根据数组生成二叉树的有向图结构\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def build(nums: List[int]):\n",
    "        n = len(nums)\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda it: nums[it])  # 索引\n",
    "        rank = {idx: i for i, idx in enumerate(ind)}  # 排序\n",
    "\n",
    "        dct = [[] for _ in range(n)]  # 二叉树按照索引的有向图结构\n",
    "        uf = UnionFindSpecial(n)\n",
    "        post = {}\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = rank[i]\n",
    "            if x + 1 in post:\n",
    "                r = uf.find(post[x + 1])\n",
    "                dct[i].append(r)\n",
    "                uf.union(i, r)\n",
    "            if x - 1 in post:\n",
    "                r = uf.find(post[x - 1])\n",
    "                dct[i].append(r)\n",
    "                uf.union(i, r)\n",
    "            post[x] = i\n",
    "        return dct\n",
    "\n",
    "    @staticmethod\n",
    "    def build_with_stack(nums: List[int]):\n",
    "        # 模板：按顺序生成二叉树，返回二叉树的索引父子信息\n",
    "        n = len(nums)\n",
    "        # 先按照大小关系编码成 1..n\n",
    "        lst = sorted(nums)\n",
    "        dct = {num: i + 1 for i, num in enumerate(lst)}\n",
    "        ind = {num: i for i, num in enumerate(nums)}\n",
    "        order = [dct[i] for i in nums]\n",
    "        father, occur, stack = [0] * (n + 1), [0] * (n + 1), []\n",
    "        deep = [0] * (n + 1)\n",
    "        for i, x in enumerate(order, 1):\n",
    "            occur[x] = i\n",
    "        # 记录原数组索引的父子关系\n",
    "        for x, i in enumerate(occur):\n",
    "            while stack and occur[stack[-1]] > i:\n",
    "                if occur[father[stack[-1]]] < i:\n",
    "                    father[stack[-1]] = x\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                father[x] = stack[-1]\n",
    "            stack.append(x)\n",
    "\n",
    "        for x in order:\n",
    "            deep[x] = 1 + deep[father[x]]\n",
    "\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i in range(1, n + 1):\n",
    "            if father[i]:\n",
    "                u, v = father[i]-1, i-1\n",
    "                x, y = ind[lst[u]], ind[lst[v]]\n",
    "                dct[x].append(y)\n",
    "\n",
    "        return dct\n",
    "        \n",
    "\n",
    "mod = 10**9 + 7\n",
    "class Combinatorics:\n",
    "    def __init__(self, n, mod):\n",
    "        # 模板：求全排列组合数，使用时注意 n 的取值范围\n",
    "        n += 10\n",
    "        self.perm = [1] * n\n",
    "        self.rev = [1] * n\n",
    "        self.mod = mod\n",
    "        for i in range(1, n):\n",
    "            # 阶乘数 i! 取模\n",
    "            self.perm[i] = self.perm[i - 1] * i\n",
    "            self.perm[i] %= self.mod\n",
    "        self.rev[-1] = self.mod_reverse(self.perm[-1], self.mod)  # 等价于pow(self.perm[-1], -1, self.mod)\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            self.rev[i] = (self.rev[i + 1] * (i + 1) % mod)  # 阶乘 i! 取逆元\n",
    "        self.fault = [0] * n\n",
    "        self.fault_perm()\n",
    "        return\n",
    "\n",
    "    def ex_gcd(self, a, b):\n",
    "        # 扩展欧几里得求乘法逆元\n",
    "        if b == 0:\n",
    "            return 1, 0, a\n",
    "        else:\n",
    "            x, y, q = self.ex_gcd(b, a % b)\n",
    "            x, y = y, (x - (a // b) * y)\n",
    "            return x, y, q\n",
    "\n",
    "    def mod_reverse(self, a, p):\n",
    "        x, y, q = self.ex_gcd(a, p)\n",
    "        if q != 1:\n",
    "            raise Exception(\"No solution.\")   # 逆元要求a与p互质\n",
    "        else:\n",
    "            return (x + p) % p  # 防止负数\n",
    "\n",
    "    def comb(self, a, b):\n",
    "        if a < b:\n",
    "            return 0\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a] * self.rev[b] * self.rev[a - b]\n",
    "        return res % self.mod\n",
    "\n",
    "    def factorial(self, a):\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a]\n",
    "        return res % self.mod\n",
    "\n",
    "    def fault_perm(self):\n",
    "        # 求错位排列组合数\n",
    "        self.fault[0] = 1\n",
    "        self.fault[2] = 1\n",
    "        for i in range(3, len(self.fault)):\n",
    "            self.fault[i] = (i - 1) * (self.fault[i - 1] + self.fault[i - 2])\n",
    "            self.fault[i] %= self.mod\n",
    "        return\n",
    "\n",
    "    def inv(self, n):\n",
    "        # 求 pow(n, -1, mod)\n",
    "        return self.perm[n - 1] * self.rev[n] % self.mod\n",
    "\n",
    "    def catalan(self, n):\n",
    "        # 求卡特兰数\n",
    "        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod\n",
    "\n",
    "\n",
    "cb = Combinatorics(1000, mod)\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        dct = BinarySearchTreeByArray().build(nums)\n",
    "        stack = [0]\n",
    "        n = len(nums)\n",
    "        ans = [0]*n\n",
    "        sub = [0]*n\n",
    "        while stack:\n",
    "            i = stack.pop()\n",
    "            if i >= 0:\n",
    "                stack.append(~i)\n",
    "                for j in dct[i]:\n",
    "                    stack.append(j)\n",
    "            else:\n",
    "                i = ~i\n",
    "                cur_ans = 1\n",
    "                cur_sub = sum(sub[j] for j in dct[i])\n",
    "                sub[i] = cur_sub + 1\n",
    "                for j in dct[i]:\n",
    "                    cur_ans *= cb.comb(cur_sub, sub[j])*ans[j]\n",
    "                    cur_sub -= sub[j]\n",
    "                    cur_ans %= mod\n",
    "                ans[i] = cur_ans\n",
    "        return (ans[0] - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\r\n",
    "mod = 1000000007\r\n",
    "class Node:\r\n",
    "    def __init__(self, val: int) -> None:\r\n",
    "        self.val = val\r\n",
    "        self.nxt: Node = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def numOfWays(self, nums: List[int]) -> int:\r\n",
    "        head: Node = None\r\n",
    "        runner: Node = None\r\n",
    "        for num in nums:\r\n",
    "            if head is None:\r\n",
    "                head = Node(num)\r\n",
    "                runner = head\r\n",
    "            else:\r\n",
    "                runner.nxt = Node(num)\r\n",
    "                runner = runner.nxt\r\n",
    "        \r\n",
    "        def divide(node: Node) -> int:\r\n",
    "            lft: Node = None\r\n",
    "            rgt: Node = None\r\n",
    "            p: Node = None\r\n",
    "            q: Node = None\r\n",
    "            root = node.val\r\n",
    "            node = node.nxt\r\n",
    "            n = 0\r\n",
    "            l = 0\r\n",
    "\r\n",
    "            while node is not None:\r\n",
    "                n += 1\r\n",
    "                if node.val < root:\r\n",
    "                    l += 1\r\n",
    "                    if lft is None:\r\n",
    "                        lft = node\r\n",
    "                        p = lft\r\n",
    "                    else:\r\n",
    "                        p.nxt = node\r\n",
    "                        p = p.nxt\r\n",
    "                else:\r\n",
    "                    if rgt is None:\r\n",
    "                        rgt = node\r\n",
    "                        q = rgt\r\n",
    "                    else:\r\n",
    "                        q.nxt = node\r\n",
    "                        q = q.nxt\r\n",
    "                node = node.nxt\r\n",
    "\r\n",
    "            ret = comb(n, l)\r\n",
    "            if p is not None:\r\n",
    "                p.nxt = None\r\n",
    "                ret *= divide(lft)\r\n",
    "            if q is not None:\r\n",
    "                q.nxt = None\r\n",
    "                ret *= divide(rgt)\r\n",
    "\r\n",
    "            return ret % mod\r\n",
    "        \r\n",
    "        return (mod + divide(head) - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "\n",
    "        def insert(node):\n",
    "            if num > node.val:\n",
    "                if node.right:\n",
    "                    insert(node.right)\n",
    "                else:\n",
    "                    node.right = TreeNode(num)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    insert(node.left)\n",
    "                else:\n",
    "                    node.left = TreeNode(num)\n",
    "            return\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return [1, 0]\n",
    "            if not node.left and not node.right:\n",
    "                return [1, 1]\n",
    "            res = [1, 1]\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            res[1] += left[1] + right[1]\n",
    "            res[0] = left[0] * right[0] * math.comb(res[1] - 1, left[1])\n",
    "            res[0] %= MOD\n",
    "            return res\n",
    "\n",
    "        # 建立二叉搜索树\n",
    "        root = TreeNode(nums[0])\n",
    "        for num in nums[1:]:\n",
    "            insert(root)\n",
    "\n",
    "        # 使用树形DP进行方案数计算\n",
    "        ans = (dfs(root)[0] - 1) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def insert(self, val):\n",
    "        if val < self.val:\n",
    "            if self.left:\n",
    "                self.left.insert(val)\n",
    "            else:\n",
    "                self.left = Tree(val)\n",
    "        else:\n",
    "            if self.right:\n",
    "                self.right.insert(val)\n",
    "            else:\n",
    "                self.right = Tree(val)\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        root = Tree(nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            root.insert(nums[i])\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 1, 0\n",
    "            a1, b1 = dfs(node.left)\n",
    "            a2, b2 = dfs(node.right)\n",
    "            return a1 * a2 * comb(b1 + b2, b1) % (10 ** 9 + 7), b1 + b2 + 1\n",
    "        return dfs(root)[0] - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode():\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        def add(x, val):\n",
    "            if val < x.val:\n",
    "                if x.left:\n",
    "                    add(x.left, val)\n",
    "                else:\n",
    "                    x.left = TreeNode(val)\n",
    "            else:\n",
    "                if x.right:\n",
    "                    add(x.right, val)\n",
    "                else:\n",
    "                    x.right = TreeNode(val)\n",
    "\n",
    "        def f(n):\n",
    "            res = 1\n",
    "            while n > 1:\n",
    "                res *= n\n",
    "                n-=1\n",
    "            return res\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x is None:\n",
    "                return 1, 0\n",
    "            l, xx = dfs(x.left)\n",
    "            r, yy = dfs(x.right)\n",
    "\n",
    "            res = f(xx+yy)//(f(xx) * f(yy)) * l * r\n",
    "            res %= MOD\n",
    "\n",
    "            return res, xx + yy + 1\n",
    "\n",
    "        root = TreeNode(nums[0])\n",
    "        for n in nums[1:]:\n",
    "            add(root, n)\n",
    "        \n",
    "        return dfs(root)[0] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        def dfs(nums: List[int]):\n",
    "            \"\"\"number of ways to reorder `nums` array to get same BST\"\"\"\n",
    "            if len(nums) < 3: \n",
    "                return 1\n",
    "            left_nums = [num for num in nums if num < nums[0]]\n",
    "            right_nums = [num for num in nums if num > nums[0]]\n",
    "            left_ct = dfs(left_nums)\n",
    "            right_ct = dfs(right_nums)\n",
    "            count = math.comb(len(nums) - 1, len(left_nums)) * left_ct * right_ct\n",
    "            return count \n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        return (dfs(nums) - 1) % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        \n",
    "        \n",
    "        def solve(arr):\n",
    "            n=len(arr)\n",
    "            if n<=1: return 1\n",
    "            g=[]\n",
    "            l=[]\n",
    "            for i in range(1,n):\n",
    "                if arr[i]>arr[0]: g.append(arr[i])\n",
    "                else: l.append(arr[i])\n",
    "            \n",
    "            return comb(n-1,len(g))%MOD*solve(l)%MOD*solve(g)%MOD\n",
    "\n",
    "        return solve(nums)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        def dfs(nums: List[int]):\n",
    "            \"\"\"number of ways to reorder `nums` array to get same BST\"\"\"\n",
    "            if not nums: \n",
    "                return 1\n",
    "            left_nums = [num for num in nums if num < nums[0]]\n",
    "            right_nums = [num for num in nums if num > nums[0]]\n",
    "            left_ct = dfs(left_nums)\n",
    "            right_ct = dfs(right_nums)\n",
    "            count = math.comb(len(nums) - 1, len(left_nums)) * left_ct * right_ct\n",
    "            return count \n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        return (dfs(nums) - 1) % mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        def w(nums):\n",
    "            if len(nums) <=2 :\n",
    "                return 1\n",
    "            left = [i for i in nums if i < nums[0]]\n",
    "            right = [i for i in nums if i > nums[0]]\n",
    "            return comb(len(left)+len(right), len(left)) * w(left) * w(right)\n",
    "        return (w(nums)-1)%(10**9+7)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        def ways(arr):\n",
    "            if len(arr) <= 2: return 1\n",
    "            root = arr[0]\n",
    "            l = [x for x in arr if x < arr[0]]\n",
    "            r = [x for x in arr if x > arr[0]]\n",
    "            return comb(len(l) + len(r), len(l)) * ways(l) * ways(r)\n",
    "        \n",
    "        return (ways(nums) - 1) % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        def dfs(L):\n",
    "            if len(L) <= 2:\n",
    "                return 1\n",
    "            first = L[0]\n",
    "            less, more = [], []\n",
    "            for i in range(1, len(L)):\n",
    "                if L[i] > first:\n",
    "                    more.append(L[i])\n",
    "                else:\n",
    "                    less.append(L[i])\n",
    "            return comb(len(L) - 1, len(less)) * dfs(less) * dfs(more) % mod \n",
    "        \n",
    "        return dfs(nums) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def dfs(nums):\n",
    "            if len(nums) < 1:\n",
    "                return 1\n",
    "            small, large = [], []\n",
    "            for i in range(1, len(nums), 1):\n",
    "                if nums[i] > nums[0]:\n",
    "                    large.append(nums[i])\n",
    "                else:\n",
    "                    small.append(nums[i])\n",
    "            x, y = len(large), len(small)\n",
    "            fx = dfs(large)\n",
    "            fy = dfs(small)\n",
    "            return math.comb(x+y, x) * fx % MOD * fy % MOD\n",
    "\n",
    "        rst = dfs(nums) - 1\n",
    "        rst %= MOD\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\r\n",
    "mod = 1000000007\r\n",
    "class Solution:\r\n",
    "    def numOfWays(self, nums: List[int]) -> int:\r\n",
    "        def divide(nums: list[int]) -> int:\r\n",
    "            n = len(nums)\r\n",
    "            if n < 3: return 1\r\n",
    "            l: list[int] = list()\r\n",
    "            r: list[int] = list()\r\n",
    "            for i in range(1, n):\r\n",
    "                if nums[i] < nums[0]: l.append(nums[i])\r\n",
    "                else: r.append(nums[i])\r\n",
    "            return (divide(l) * divide(r) * comb(n - 1, len(l))) % mod\r\n",
    "        return (mod + divide(nums) - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        \n",
    "        \n",
    "        def solve(arr):\n",
    "            n=len(arr)\n",
    "            if n<=2: return 1\n",
    "            g=[]\n",
    "            l=[]\n",
    "            for i in range(1,n):\n",
    "                if arr[i]>arr[0]: g.append(arr[i])\n",
    "                else: l.append(arr[i])\n",
    "            \n",
    "            return comb(n-1,len(g))%MOD*solve(l)%MOD*solve(g)%MOD\n",
    "\n",
    "        return solve(nums)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        def dac(arr):\n",
    "            if len(arr) <= 1: return 1\n",
    "            less, more = [], []\n",
    "            for x in arr[1:]: (less if x < arr[0] else more).append(x)\n",
    "            return comb(len(arr) - 1, len(less)) * dac(less) * dac(more) % MOD\n",
    "        \n",
    "        MOD = int(1e9) + 7\n",
    "        comb = cache(math.comb)\n",
    "        return (dac(nums) - 1 + MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        def ways(nums):\n",
    "            if len(nums) <= 2: return 1\n",
    "            l = [x for x in nums if x < nums[0]]\n",
    "            r = [x for x in nums if x > nums[0]]\n",
    "            return comb(len(l) + len(r), len(l)) * ways(l) * ways(r)\n",
    "        return (ways(nums) - 1) % (10**9 +7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def numOfWays(self, nums: List[int]) -> int:\n",
    "    def ways(nums):\n",
    "      if len(nums) <= 2: return 1\n",
    "      l = [x for x in nums if x < nums[0]]\n",
    "      r = [x for x in nums if x > nums[0]]\n",
    "      return comb(len(l) + len(r), len(l)) * ways(l) * ways(r)\n",
    "    return (ways(nums) - 1) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def dfs(nums):\n",
    "            if len(nums) < 1:\n",
    "                return 1\n",
    "            small, large = [], []\n",
    "            for i in range(1, len(nums), 1):\n",
    "                if nums[i] > nums[0]:\n",
    "                    large.append(nums[i])\n",
    "                else:\n",
    "                    small.append(nums[i])\n",
    "            x, y = len(large), len(small)\n",
    "            fx = dfs(large)\n",
    "            fy = dfs(small)\n",
    "            return math.comb(x+y, x) * fx % MOD * fy % MOD\n",
    "\n",
    "        rst = dfs(nums) - 1\n",
    "        rst %= MOD\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        res = self.help(nums) - 1\n",
    "        return res%MOD\n",
    "\n",
    "    def help(self, nums:List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n<=1: return 1\n",
    "        root = nums[0]\n",
    "        left,right = [],[]\n",
    "        for num in nums:\n",
    "            if num<root: left.append(num)\n",
    "            elif num>root: right.append(num)\n",
    "        left_num = self.help(left)\n",
    "        right_num = self.help(right)\n",
    "        combi = self.cal(n-1, len(left))\n",
    "        res = left_num * right_num * combi\n",
    "        return res\n",
    "    \n",
    "    def cal(self, a, b):\n",
    "        res = 1\n",
    "        for i in range(1,b+1):\n",
    "            res = res * a\n",
    "            res = res // i\n",
    "            a -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        \n",
    "        \n",
    "        def solve(arr):\n",
    "            n=len(arr)\n",
    "            if n<=2: return 1\n",
    "            g=[]\n",
    "            l=[]\n",
    "            for i in range(1,n):\n",
    "                if arr[i]>arr[0]: g.append(arr[i])\n",
    "                else: l.append(arr[i])\n",
    "            \n",
    "            return comb(n-1,len(g))%MOD*solve(l)%MOD*solve(g)%MOD\n",
    "\n",
    "        return solve(nums)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        res = self.help(nums) - 1\n",
    "        return res%MOD\n",
    "\n",
    "    def help(self, nums:List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n<=1: return 1\n",
    "        root = nums[0]\n",
    "        left,right = [],[]\n",
    "        for num in nums:\n",
    "            if num<root: left.append(num)\n",
    "            elif num>root: right.append(num)\n",
    "        left_num = self.help(left)\n",
    "        right_num = self.help(right)\n",
    "        combi = self.cal(n-1, len(left))\n",
    "        res = left_num * right_num * combi\n",
    "        return res\n",
    "    \n",
    "    def cal(self, a, b):\n",
    "        res = 1\n",
    "        for i in range(1,b+1):\n",
    "            res = res * a\n",
    "            res = res // i\n",
    "            a -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def helper(self, nums):\n",
    "        if not nums:\n",
    "            return 1\n",
    "        n = len(nums)\n",
    "        head = nums[0]\n",
    "        small = [i for i in nums if i < head]\n",
    "        large = [i for i in nums if i > head]\n",
    "        ans = self.helper(small) * self.helper(large) * comb(len(nums) - 1, len(small))\n",
    "        return ans % MOD\n",
    "\n",
    "    \n",
    "\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        return self.helper(nums) - 1\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        from math import comb\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def f(nums):\n",
    "            if len(nums) < 3: return 1\n",
    "            left = [num for num in nums if num < nums[0]]\n",
    "            right = [num for num in nums if num > nums[0]]\n",
    "            l, r = f(left), f(right)\n",
    "            res = comb(len(nums) - 1, len(left)) * l * r\n",
    "            return res\n",
    "        \n",
    "        return (f(nums) - 1)%(10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        comb = cache(math.comb)\n",
    "        def dfs(l):\n",
    "            if len(l) <= 2:\n",
    "                return 1\n",
    "            left, right = [], []\n",
    "            for i in range(1, len(l)):\n",
    "                if l[i] < l[0]:\n",
    "                    left.append(l[i])\n",
    "                else:\n",
    "                    right.append(l[i])\n",
    "            return (dfs(right) * dfs(left) * comb(len(left) + len(right), len(left))) % mod\n",
    "        return (dfs(nums) + mod - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def f(nums):\n",
    "            if len(nums) < 3: return 1\n",
    "            left = [num for num in nums if num < nums[0]]\n",
    "            right = [num for num in nums if num > nums[0]]\n",
    "            l, r = f(left), f(right)\n",
    "            res = comb(len(nums) - 1, len(left)) * l * r\n",
    "            return res\n",
    "        \n",
    "        return (f(nums) - 1)%(10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        def dac(arr):\n",
    "            if len(arr) <= 2: \n",
    "                return 1\n",
    "            less, more = [], []\n",
    "            for x in arr[1:]: \n",
    "                (less if x < arr[0] else more).append(x)\n",
    "            return comb(len(arr) - 1, len(less)) * dac(less) * dac(more) % MOD\n",
    "        \n",
    "        MOD = int(1e9) + 7\n",
    "        comb = cache(math.comb)\n",
    "        return (dac(nums) - 1 + MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def f(nums):\n",
    "            if len(nums) < 3: return 1\n",
    "            left = [num for num in nums if num < nums[0]]\n",
    "            right = [num for num in nums if num > nums[0]]\n",
    "            l, r = f(left), f(right)\n",
    "            res = comb(len(nums) - 1, len(left)) * l * r\n",
    "            return res\n",
    "        \n",
    "        return (f(nums) - 1)%(10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "mod = 10**9 + 7\n",
    "class Combinatorics:\n",
    "    def __init__(self, n, mod):\n",
    "        # 模板：求全排列组合数，使用时注意 n 的取值范围\n",
    "        n += 10\n",
    "        self.perm = [1] * n\n",
    "        self.rev = [1] * n\n",
    "        self.mod = mod\n",
    "        for i in range(1, n):\n",
    "            # 阶乘数 i! 取模\n",
    "            self.perm[i] = self.perm[i - 1] * i\n",
    "            self.perm[i] %= self.mod\n",
    "        self.rev[-1] = self.mod_reverse(self.perm[-1], self.mod)  # 等价于pow(self.perm[-1], -1, self.mod)\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            self.rev[i] = (self.rev[i + 1] * (i + 1) % mod)  # 阶乘 i! 取逆元\n",
    "        self.fault = [0] * n\n",
    "        self.fault_perm()\n",
    "        return\n",
    "\n",
    "    def ex_gcd(self, a, b):\n",
    "        # 扩展欧几里得求乘法逆元\n",
    "        if b == 0:\n",
    "            return 1, 0, a\n",
    "        else:\n",
    "            x, y, q = self.ex_gcd(b, a % b)\n",
    "            x, y = y, (x - (a // b) * y)\n",
    "            return x, y, q\n",
    "\n",
    "    def mod_reverse(self, a, p):\n",
    "        x, y, q = self.ex_gcd(a, p)\n",
    "        if q != 1:\n",
    "            raise Exception(\"No solution.\")   # 逆元要求a与p互质\n",
    "        else:\n",
    "            return (x + p) % p  # 防止负数\n",
    "\n",
    "    def comb(self, a, b):\n",
    "        if a < b:\n",
    "            return 0\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a] * self.rev[b] * self.rev[a - b]\n",
    "        return res % self.mod\n",
    "\n",
    "    def factorial(self, a):\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a]\n",
    "        return res % self.mod\n",
    "\n",
    "    def fault_perm(self):\n",
    "        # 求错位排列组合数\n",
    "        self.fault[0] = 1\n",
    "        self.fault[2] = 1\n",
    "        for i in range(3, len(self.fault)):\n",
    "            self.fault[i] = (i - 1) * (self.fault[i - 1] + self.fault[i - 2])\n",
    "            self.fault[i] %= self.mod\n",
    "        return\n",
    "\n",
    "    def inv(self, n):\n",
    "        # 求 pow(n, -1, mod)\n",
    "        return self.perm[n - 1] * self.rev[n] % self.mod\n",
    "\n",
    "    def catalan(self, n):\n",
    "        # 求卡特兰数\n",
    "        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod\n",
    "\n",
    "\n",
    "cb = Combinatorics(1000, mod)\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "\n",
    "        def dfs(lst):\n",
    "            if len(lst) <= 1:\n",
    "                return 1\n",
    "            root = lst[0]\n",
    "            left = [num for num in lst[1:] if num < root]\n",
    "            right = [num for num in lst[1:] if num > root]\n",
    "            x = dfs(left)\n",
    "            y = dfs(right)\n",
    "            ans = cb.comb(len(lst)-1, len(left))*x*y\n",
    "            ans %= mod\n",
    "            return ans\n",
    "        return (dfs(nums[:])-1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        mod= 10**9 + 7\n",
    "        def dfs(ls):\n",
    "            if len(ls)==0:\n",
    "                return 1,0\n",
    "            if len(ls)==1:\n",
    "                return 1,1\n",
    "            ll,lr=[],[]\n",
    "            for k in ls:\n",
    "                if k<ls[0]:\n",
    "                    ll.append(k)\n",
    "                if k>ls[0]:\n",
    "                    lr.append(k)\n",
    "            l,lnum=dfs(tuple(ll))\n",
    "            r,rnum=dfs(tuple(lr))\n",
    "            return l*r*math.comb(lnum+rnum,lnum),lnum+rnum+1\n",
    "        \n",
    "        return int(dfs(tuple(nums))[0])%mod-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.size = 1\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        MOD = int(1e9) + 7\n",
    "\n",
    "        bst = Node(nums[0])\n",
    "\n",
    "        def insert(x, root):\n",
    "            root.size += 1\n",
    "            if x < root.val:\n",
    "                if root.left:\n",
    "                    insert(x, root.left)\n",
    "                else:\n",
    "                    root.left = Node(x)\n",
    "            else:\n",
    "                if root.right:\n",
    "                    insert(x, root.right)\n",
    "                else:\n",
    "                    root.right = Node(x)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            x = nums[i]\n",
    "            insert(x, bst)\n",
    "\n",
    "        @cache\n",
    "        def c(n, k):\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            if n == k:\n",
    "                return 1\n",
    "\n",
    "            return c(n - 1, k) + c(n - 1, k - 1)\n",
    "\n",
    "        @cache\n",
    "        def dp(x):\n",
    "            if not x:\n",
    "                return 1\n",
    "            \n",
    "            if x.left:\n",
    "                return (c(x.size - 1, x.left.size) * dp(x.left) * dp(x.right)) % MOD\n",
    "\n",
    "            return dp(x.right)\n",
    "\n",
    "        return (dp(bst) + MOD - 1) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TNode:\n",
    "    def __init__(self, val):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.value = val\n",
    "        self.size = 1\n",
    "        self.ans = 0\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        def insert(val: int):\n",
    "            cur = root\n",
    "            while True:\n",
    "                cur.size += 1\n",
    "                if val < cur.value:\n",
    "                    if not cur.left:\n",
    "                        cur.left = TNode(val)\n",
    "                        return\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    if not cur.right:\n",
    "                        cur.right = TNode(val)\n",
    "                        return\n",
    "                    cur = cur.right\n",
    "        \n",
    "        def dfs(node: TNode):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            lsize = node.left.size if node.left else 0\n",
    "            rsize = node.right.size if node.right else 0\n",
    "            lans = node.left.ans if node.left else 1\n",
    "            rans = node.right.ans if node.right else 1\n",
    "            node.ans = c[lsize + rsize][lsize] * lans * rans % mod\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        c = [[0] * n for _ in range(n)]\n",
    "        c[0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            c[i][0] = 1\n",
    "            for j in range(1, n):\n",
    "                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod\n",
    "\n",
    "        root = TNode(nums[0])\n",
    "        for i in range(1, n):\n",
    "            val = nums[i]\n",
    "            insert(val)\n",
    "\n",
    "        dfs(root)\n",
    "        return (root.ans - 1 + mod) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TNode:\n",
    "    def __init__(self, val):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.value = val\n",
    "        self.size = 1\n",
    "        self.ans = 0\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        def insert(val: int):\n",
    "            cur = root\n",
    "            while True:\n",
    "                cur.size += 1\n",
    "                if val < cur.value:\n",
    "                    if not cur.left:\n",
    "                        cur.left = TNode(val)\n",
    "                        return\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    if not cur.right:\n",
    "                        cur.right = TNode(val)\n",
    "                        return\n",
    "                    cur = cur.right\n",
    "        \n",
    "        def dfs(node: TNode):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            lsize = node.left.size if node.left else 0\n",
    "            rsize = node.right.size if node.right else 0\n",
    "            lans = node.left.ans if node.left else 1\n",
    "            rans = node.right.ans if node.right else 1\n",
    "            node.ans = c[lsize + rsize][lsize] * lans * rans % mod\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        c = [[0] * n for _ in range(n)]\n",
    "        c[0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            c[i][0] = 1\n",
    "            for j in range(1, n):\n",
    "                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod\n",
    "\n",
    "        root = TNode(nums[0])\n",
    "        for i in range(1, n):\n",
    "            val = nums[i]\n",
    "            insert(val)\n",
    "\n",
    "        dfs(root)\n",
    "        return (root.ans - 1 + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        class TreeNode:\n",
    "            def __init__(self, value):\n",
    "                self.mValue = value\n",
    "                self.left = None\n",
    "                self.right = None\n",
    "                self.size = 1\n",
    "                self.ans = 0\n",
    "            # def value(self):\n",
    "            #     return self.mValue\n",
    "\n",
    "            # def left(self):\n",
    "            #     return self.left\n",
    "\n",
    "            # def right(self):\n",
    "            #     return self.right\n",
    "\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        root = TreeNode(nums[0])\n",
    "        # print(root.mValue)\n",
    "        length = len(nums)\n",
    "        for i in range(1, length):\n",
    "            pos = root\n",
    "            v = nums[i]\n",
    "            while pos is not None:\n",
    "                pos.size += 1\n",
    "                if v < pos.mValue:\n",
    "                    if pos.left is None:\n",
    "                        pos.left = TreeNode(v)\n",
    "                        # print(root.left.mValue)\n",
    "                        break\n",
    "                    else:\n",
    "                        pos = pos.left \n",
    "                else:\n",
    "                    if pos.right is None:\n",
    "                        pos.right = TreeNode(v)\n",
    "                        break\n",
    "                    else:\n",
    "                        pos = pos.right\n",
    "\n",
    "        # print(root.left, root.right)\n",
    "        \n",
    "        # global rs_count\n",
    "        # rs_count = 0\n",
    "        # my_queue = [root]\n",
    "        # print(root)\n",
    "        # print(type(root.left))\n",
    "        # print(root.left.mValue)\n",
    "        # my_list = []\n",
    "        # def digui(q, l):\n",
    "        #     global rs_count\n",
    "        #     # print(len(l))\n",
    "        #     if len(l) == length:\n",
    "        #         rs_count += 1\n",
    "        #     tmp_queue = q.copy()\n",
    "        #     for i_, v_ in enumerate(tmp_queue):\n",
    "        #         q.pop(i_)\n",
    "        #         l.append(v_.mValue)\n",
    "        #         child_count = 0\n",
    "        #         # print(v_.left, v_.right)\n",
    "        #         if v_.left is not None:\n",
    "        #             child_count += 1\n",
    "        #             q.append(v_.left)\n",
    "        #         if v_.right is not None:\n",
    "        #             child_count += 1\n",
    "        #             q.append(v_.right)\n",
    "        #         digui(q, l)\n",
    "        #         for _ in range(child_count):\n",
    "        #             q.pop(-1)\n",
    "        #         q.insert(i_, v_)\n",
    "        #         l.pop(-1)\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "            lsize = node.left.size if node.left is not None else 0\n",
    "            rsize = node.right.size if node.right is not None else 0\n",
    "            lans = node.left.ans if node.left else 1\n",
    "            rans = node.right.ans if node.right else 1\n",
    "            node.ans = c[lsize + rsize][lsize] * lans * rans % mod\n",
    "\n",
    "        c = [[0] * length for _ in range(length)]\n",
    "        c[0][0] = 1\n",
    "        for i in range(1, length):\n",
    "            c[i][0] = 1\n",
    "            for j in range(1, length):\n",
    "                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod\n",
    "\n",
    "\n",
    "\n",
    "        dfs(root)\n",
    "        return (root.ans - 1 + mod) % mod\n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left, self.right = None, None\n",
    "        self.size, self.ans = 1, 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    key:\n",
    "        1.C(m+n,n) = C(m+n-1,n) + C(m+n-1,n-1)  C(x,1) = x, C(x,0) = 1\n",
    "        2.乘法原理\n",
    "    \"\"\"\n",
    "    MOD = 10 ** 9 + 7\n",
    "\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        root = TNode(nums[0])\n",
    "\n",
    "        def insert(val):\n",
    "            cur = root\n",
    "            while cur is not None:\n",
    "                if val > cur.val:\n",
    "                    if cur.right is None:\n",
    "                        cur.right = TNode(val)\n",
    "                        return\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    if cur.left is None:\n",
    "                        cur.left = TNode(val)\n",
    "                        return\n",
    "                    cur = cur.left\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            insert(nums[i])\n",
    "\n",
    "        def dfs(cur_node: TNode) -> int:\n",
    "            if cur_node is None:\n",
    "                return 0\n",
    "\n",
    "            l_size = dfs(cur_node.left)\n",
    "            r_size = dfs(cur_node.right)\n",
    "\n",
    "            total_size = l_size + r_size + 1\n",
    "            cur_node.size = total_size\n",
    "\n",
    "            l_ans = cur_node.left.ans if cur_node.left else 1\n",
    "            r_ans = cur_node.right.ans if cur_node.right else 1\n",
    "            cur_node.ans = c[l_size + r_size][l_size] * l_ans * r_ans % self.MOD\n",
    "            return total_size\n",
    "\n",
    "        c = [[0] * n for _ in range(n)]\n",
    "        c[0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            c[i][0] = 1\n",
    "            for j in range(1, n):\n",
    "                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % self.MOD\n",
    "\n",
    "        dfs(root)\n",
    "        return (root.ans - 1) % self.MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, value) -> None:\n",
    "        self.value = value\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.ans = 0\n",
    "        self.count = 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        root = TreeNode(nums[0])\n",
    "\n",
    "        def insert(val):\n",
    "            cur = root\n",
    "            while True:\n",
    "                cur.count += 1\n",
    "                if val > cur.value:\n",
    "\n",
    "                    if cur.right is None:\n",
    "                        cur.right = TreeNode(val)\n",
    "                        return\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "\n",
    "                    if cur.left is None:\n",
    "                        cur.left = TreeNode(val)\n",
    "                        return\n",
    "                    cur = cur.left\n",
    "\n",
    "        for i in range(1, n):\n",
    "            insert(nums[i])\n",
    "        c = [[0] * n for _ in range(n)]\n",
    "        c[0][0] = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            c[i][0] = 1\n",
    "            for j in range(1, n):\n",
    "                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "\n",
    "\n",
    "\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            left_cnt = node.left.count if node.left else 0\n",
    "            right_cnt = node.right.count if node.right else 0\n",
    "            left_ans = node.left.ans if node.left else 1\n",
    "            right_ans = node.right.ans if node.right else 1\n",
    "\n",
    "            value = (c[left_cnt + right_cnt][left_cnt] * (left_ans * right_ans)) % mod\n",
    "           # print('node', node.value, '-', value)\n",
    "            node.ans = value\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return (root.ans - 1 + mod) % mod"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
